package com.sheng.leetcode.year2023.month11.day28;

import org.junit.Test;

import java.util.LinkedList;

/**
 * @author by ls
 * @date 2023/11/28
 * <p>
 * 1670. 设计前中后队列<p>
 * <p>
 * 请你设计一个队列，支持在前，中，后三个位置的 push 和 pop 操作。<p>
 * 请你完成 FrontMiddleBack 类：<p>
 * FrontMiddleBack() 初始化队列。<p>
 * void pushFront(int val) 将 val 添加到队列的 最前面 。<p>
 * void pushMiddle(int val) 将 val 添加到队列的 正中间 。<p>
 * void pushBack(int val) 将 val 添加到队里的 最后面 。<p>
 * int popFront() 将 最前面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。<p>
 * int popMiddle() 将 正中间 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。<p>
 * int popBack() 将 最后面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。<p>
 * 请注意当有 两个 中间位置的时候，选择靠前面的位置进行操作。比方说：<p>
 * 将 6 添加到 [1, 2, 3, 4, 5] 的中间位置，结果数组为 [1, 2, 6, 3, 4, 5] 。<p>
 * 从 [1, 2, 3, 4, 5, 6] 的中间位置弹出元素，返回 3 ，数组变为 [1, 2, 4, 5, 6] 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：<p>
 * ["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]<p>
 * [[], [1], [2], [3], [4], [], [], [], [], []]<p>
 * 输出：<p>
 * [null, null, null, null, null, 1, 3, 4, 2, -1]<p>
 * 解释：<p>
 * FrontMiddleBackQueue q = new FrontMiddleBackQueue();<p>
 * q.pushFront(1);   // [1]<p>
 * q.pushBack(2);    // [1, 2]<p>
 * q.pushMiddle(3);  // [1, 3, 2]<p>
 * q.pushMiddle(4);  // [1, 4, 3, 2]<p>
 * q.popFront();     // 返回 1 -> [4, 3, 2]<p>
 * q.popMiddle();    // 返回 3 -> [4, 2]<p>
 * q.popMiddle();    // 返回 4 -> [2]<p>
 * q.popBack();      // 返回 2 -> []<p>
 * q.popFront();     // 返回 -1 -> [] （队列为空）<p>
 * <p>
 * 提示：<p>
 * 1 <= val <= 10^9<p>
 * 最多调用 1000 次 pushFront， pushMiddle， pushBack， popFront， popMiddle 和 popBack 。<p>
 */
public class LeetCode1670 {

    @Test
    public void test01() {
        FrontMiddleBackQueue q = new FrontMiddleBackQueue();
        q.pushFront(1);   // [1]
        q.pushBack(2);    // [1, 2]
        q.pushMiddle(3);  // [1, 3, 2]
        q.pushMiddle(4);  // [1, 4, 3, 2]
        System.out.println(q.popFront());     // 返回 1 -> [4, 3, 2]
        System.out.println(q.popMiddle());    // 返回 3 -> [4, 2]
        System.out.println(q.popMiddle());    // 返回 4 -> [2]
        System.out.println(q.popBack());      // 返回 2 -> []
        System.out.println(q.popFront());     // 返回 -1 -> [] （队列为空）
    }
}

class FrontMiddleBackQueue {

    LinkedList<Integer> left, right;

    /**
     * 初始化队列
     */
    public FrontMiddleBackQueue() {
        // 保证左边集合的长度小于等于右边集合
        left = new LinkedList<>();
        right = new LinkedList<>();
    }

    /**
     * 将 val 添加到队列的 最前面
     *
     * @param val
     */
    public void pushFront(int val) {
        // 添加到左集合的第一个
        left.addFirst(val);
        if (left.size() > right.size()) {
            // 将左集合的最后一个元素，放到右集合的第一个位置
            right.addFirst(left.removeLast());
        }
    }

    /**
     * 将 val 添加到队列的 正中间
     *
     * @param val
     */
    public void pushMiddle(int val) {
        if (left.size() == right.size()) {
            // 添加到右集合的第一个
            right.addFirst(val);
        } else {
            // 添加到左集合的最后一个
            left.addLast(val);
        }
    }

    /**
     * 将 val 添加到队里的 最后面
     *
     * @param val
     */
    public void pushBack(int val) {
        // 添加到右集合的最后
        right.addLast(val);
        if (right.size() > left.size() + 1) {
            // 将右集合的第一个元素，添加到左集合的最后面
            left.addLast(right.removeFirst());
        }
    }

    /**
     * 将 最前面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1
     *
     * @return
     */
    public int popFront() {
        if (!left.isEmpty()) {
            // 左集合不为空的时候，移除左集合的第一个元素
            Integer first = left.removeFirst();
            // 判断，并平衡
            if (right.size() > left.size() + 1) {
                left.addLast(right.removeFirst());
            }
            return first;
        }
        // 左集合为空，右集合不为空的时候，移除右集合的第一个元素
        if (!right.isEmpty()) {
            return right.removeFirst();
        }
        return -1;
    }

    /**
     * 将 正中间 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1
     *
     * @return
     */
    public int popMiddle() {
        if (!right.isEmpty()) {
            if (left.size() == right.size()) {
                // 相等时，移除左边的最后一个元素
                return left.removeLast();
            } else {
                // 否则移除右边的第一个元素
                return right.removeFirst();
            }
        }
        return -1;
    }

    /**
     * 将 最后面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1
     *
     * @return
     */
    public int popBack() {
        if (!right.isEmpty()) {
            // 移除右集合的最后一个元素
            Integer last = right.removeLast();
            // 判断并进行平衡
            if (left.size() > right.size()) {
                right.addFirst(left.removeLast());
            }
            return last;
        }
        return -1;
    }
}

/**
 * Your FrontMiddleBackQueue object will be instantiated and called as such:
 * FrontMiddleBackQueue obj = new FrontMiddleBackQueue();
 * obj.pushFront(val);
 * obj.pushMiddle(val);
 * obj.pushBack(val);
 * int param_4 = obj.popFront();
 * int param_5 = obj.popMiddle();
 * int param_6 = obj.popBack();
 */
